#include <stdio.h>
#include <stdlib.h>
//线性表之单链表
typedef int ElemType;
//1️⃣结构体的声明：头结点的声明
typedef struct node  //标签不可省略，因为在声明中要用到结构体类型，没有标签结构体类型不正确
{
    //数据域:存储的数据信息
    ElemType data;
    //指针域:指向后继的地址
    struct node * next;  //next是一个struct node *类型的指针变量
}Node;
//2️⃣初始化:创建头节点
Node *Initlist()
{
    Node *head=(Node *)malloc(sizeof(Node));
    head->data=0;
    head->next=NULL;
    return head; //返回头节点的地址
}
//3️⃣插入
//①头插法（前插法）：每个元素都插入到头节点之后
//特点：头插法顺序和排序是相反的，先插入的排在后面(离头节点远的地方)，后插入的反之
void addhead(Node *ps,ElemType n)
{
    //首先要给新节点分配一个空间，来存放数据域和指针域
    Node *p=(Node *)malloc(sizeof(Node));   //p是存放新节点指针的指针变量
    //然后将数据存进数据域
    p->data=n;
    //再将头节点后面的元素地址存入要插入的元素的指针域，即要插入的元素指针域指向原本头结点指针域指向的元素
    p->next=ps->next;
    //再让头节点指针域指向要插入的元素的地址，即头节点存储新元素的地址
    ps->next=p;
}
//②尾插法（后插法）：每个元素都插到尾节点之后，最后插入的成为新的尾节点
//特点：顺序一致
void addtail(Node *ps,ElemType n)
{
    //首先要给新节点分配一个空间，来存放数据域和指针域
    Node *p=(Node *)malloc(sizeof(Node));   //p是存放新节点指针的指针变量
    //然后将数据存进数据域
    p->data=n;
    //找到尾节点：遍历寻找指针域为NULL的节点
    Node *q=ps; //q指向头节点，从头结点开始向后一个一个找
    while(q->next)   //结点指针域为空，跳出循环，此时q存放尾结点的地址
    {
        q=q->next;
    } 
    //让尾节点的指针域存放新结点的地址
    q->next=p;
    //最后让新节点的指针域置空
    p->next=NULL;
}
//4️⃣打印
void printlist(Node *ps)
{
    Node *p=ps->next; //p指向 头节点指向的节点(第一个节点)
    while(p)    //当p=NULL，值为0，跳出循环
    {
        printf("%d ",p->data);
        p=p->next;  //p指向下一个节点，一直往下走直到p=NULL
    }
    printf("\n");
}
//5️⃣插入：由于头结点的存在，插到第n个位置就是第n个节点
void addlist(Node *ps,int n,ElemType m)
{
    //首先要给新节点分配一个空间，来存放数据域和指针域
    Node *p=(Node *)malloc(sizeof(Node));   //p是存放新节点指针的指针变量
    //然后将数据存进数据域
    p->data=m;
    //找到前一个结点：遍历
    int i;
    Node *q=ps;
    for(i=0;i<n-1;i++)  //循环n-1次
    {
        q=q->next;   //进来循环第一次q指向第一个节点，第二次q指向第二个节点
    } //最终q指向第n-1个节点
    //让新节点的指针域存放前一个结点的指针域
    p->next=q->next;
    //再让前一个结点的指针域存放新结点的地址
    q->next=p;
}
//6️⃣查找
int findlist(Node *ps,ElemType i)
{
    //遍历
    Node *q=ps->next;  //从第一个节点开始
    int count=0;
    while(q)
    {
        if(q->data!=i)
        {
            count++;
            q=q->next;
        }
        else
        {
            count++;
            return count;
        }
    }
    return 0; 
}
//7️⃣删除:删除第a个结点的内容
int deletelist(Node *ps,int a)
{
    //遍历找到a-1节点
    Node*q=ps; //q指向头节点
    int i;
    for(i=0;i<a-1;i++)
    {
        q=q->next;
    }  //最终q指向a-1节点
    Node *p=q->next; //p是存放a节点地址的指针变量
    if(p==NULL)
    {
        printf("位置不合理\n");
        return 0;
    }
    //让a-1节点的指针域存放要删除结点的指针域
    q->next=p->next;
    free(p);
    return 1;
}
//8️⃣释放链表(头节点也被释放)
void freelist(Node *ps)
{
    Node *p=ps;
    Node *q;
    while(p)
    {
        q=p->next;
        free(p);
        p=q;
    }
}
int main()
{
    Node *list=Initlist();//list是存储头节点地址的指针变量
    //插入：因为现在只有一个头结点，所以要将每个元素插入链接中
    //头插法
    addhead(list,22);
    addhead(list,66);
    //打印
    printlist(list);
    //尾插法
    addtail(list,88);
    addtail(list,94);
    //打印
    printlist(list);
    //插入：在链表中随机插入
    int n;      //插到第n个元素那
    ElemType m; //插入的数据是m
    scanf("%d %d",&n,&m);
    addlist(list,n,m);
    //打印
    printlist(list);
    //查找
    ElemType i;
    scanf("%d",&i);
    int ret=findlist(list,i);
    if(ret!=0)
    {
        printf("是第%d个元素\n",ret);
    }
    else
    {
        printf("链表中不存在\n");
    }
    //删除
    int a;
    scanf("%d",&a);
    deletelist(list,a);
    //打印
    printlist(list);
    //释放链表
    //注意，顺序表是连续存储，而链表的list只是头节点地址，free(list)无法释放整个链表，只能释放头节点
    freelist(list); 
    return 0;
}